package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.LinkedList;

public class MaximalRectangle {

    /**
     * 暴力破解
     * 首先计算出矩阵的每个元素的左边连续 1 的数量, 存放在二维数组rec中
     * 当考察以 matrix[i][j] 为右下角的矩形时，此时矩阵的最大宽度就为 res[0:i][j] 的最小值。
     *
     */
    public int maximalRectangle1(char[][] matrix) {
        if (matrix.length == 0){
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] rec = new int[m][n];
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n;++j){
                if (matrix[i][j] == '1'){
                    rec[i][j] = (j == 0 ? 0 : rec[i][j - 1]) + 1;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n;++j){
                int k = i;
                int minW = rec[k][j];
                while (k >= 0 && rec[k][j] != 0){
                    minW = Math.min(minW, rec[k][j]);
                    max = Math.max(minW * (i - k + 1), max);
                    k--;
                }
            }
        }
        return max;
    }

    /**
     * 单调栈
     */
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0){
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] rec = new int[m][n];
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n;++j){
                if (matrix[i][j] == '1'){
                    rec[i][j] = (j == 0 ? 0 : rec[i][j - 1]) + 1;
                }
            }
        }
        PrintUtils.println(rec);
        LinkedList<Integer> stack = new LinkedList<>();
        int max = 0;
        for (int j = 0; j < n;++j){
            int[] up = new int[m];
            int[] down = new int[m];
            stack.clear();
            for (int i = 0; i < m; ++i){
                while (!stack.isEmpty() && rec[stack.peek()][j] >= rec[i][j]){
                    stack.pop();
                }
                up[i] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(i);
            }
            stack.clear();
            for (int i = m - 1; i >= 0; --i){
                while (!stack.isEmpty() && rec[stack.peek()][j] >= rec[i][j]){
                    stack.pop();
                }
                down[i] = stack.isEmpty() ? m : stack.peek();
                stack.push(i);
            }
            for (int i = 0; i < m; ++i){
                max = Math.max((down[i] - up[i] - 1) * rec[i][j], max);
            }
        }
        return max;
    }


    public static void main(String[] args) {
        char[][] matrix = ArrayUtils.parseArray("" +
//                "[[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]\n" +
                "[[\"1\",\"1\",\"1\",\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\",\"1\",\"1\",\"0\"],[\"1\",\"1\",\"1\",\"1\",\"1\",\"1\",\"1\",\"0\"],[\"1\",\"1\",\"1\",\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"1\",\"1\",\"1\",\"1\",\"0\",\"0\",\"0\"]]" +
                "", char[].class);
        PrintUtils.println(matrix);
        int i = new MaximalRectangle().maximalRectangle(matrix);
        System.out.println(i);
    }
}
